/*
Implement strStr().

Returns a pointer to the first occurrence of needle in haystack, or null if needle is not part of haystack.
*/

class Solution {
public:
    char *strStr(char *haystack, char *needle) {
        if (!*needle) return haystack;	// corner case: “”
        char *p1 = (char*)haystack, *p2 = (char*)needle;
        char *p1Adv = (char*)haystack;
        while (*++p2) {
            if (!*p1Adv) return NULL;
            p1Adv++;
        }
        for (; *p1Adv; p1Adv++) {
            char *p1Begin = p1;
            p2 = (char*)needle;
            while (*p1 && *p2 && *p1 == *p2) { p1++; p2++; }
            if (!*p2) return p1Begin;
            p1 = p1Begin + 1;
        }
        return NULL;
    }
};
